;;;; 2007-02-08 21:20:38
;;;; This is your lisp file. May it serve you well.

;(in-package :cse517a-hw1)

(defun sum (lst)
  (let ((total 0))
    (dolist (val lst)
      (if (numberp val)
          (setf total (+ val total))))
    total))

(defun sum (lst)
  (if lst
      (+ (car lst) (sum (cdr lst)))
      0))

(defun mean (lst)
  (/ (sum lst) (length lst)))

(defun nth-mean (lst val)
  (mean (nth val (invert-list lst))))

#+nil(defun stddev (lst)
  (let ((m (mean lst)) (dev 0)
      (dolist (val lst)
        (if (numberp val)
          (setf dev (+ dev (abs (- val m))))))
      (/ dev (length lst)))))

(defun variance (lst)
  (let ((m (mean lst)) (dev 0))
      (dolist (val lst)
        (if (numberp val)
          (setf dev (+ dev (expt (- val m) 2)))))
      (/ dev (length lst))))

(defun stddev (lst)
  (sqrt (variance lst)))

(defun invert-list (lst)
  (let ((r nil))
    (progn
      (dotimes (i (length (car lst)))
        (setf r (cons (list ) r)))
      (dolist (sub lst)
        (dotimes (i (length sub))
          (setf (nth i r) (cons (nth i sub) (nth i r)))))
      r)))




(defun stddev-list (lst)
  (let ((devs nil))
    (progn
      (dolist (cur lst)
        (setf devs (cons (stddev cur) devs)))
      (reverse devs))))
#| comm

jkhi ent |#
(defun stddev-list (lst)
  (mapcar #'stddev lst))

(defun rands (count range)
  (let ((r (list )))
    (dotimes (i count)
      (setf r (cons (random range) r)))
    r))

(defun rands (count range)
  (if (> count 0)
      (cons (random range) (rands (1- count) range))
      nil))

(defun rands (count range &optional sofar)
  (if (> count 0)
      (rands (1- count) range (cons (random range) sofar))
      sofar))

(defun randbin (count)
  (if (> count 1)
    (cons (random 10) (randbin (- count 1)))
    (cons (random 10) nil)))

(defun read-lists (file)
  (let ((lst nil))
    (progn
      (with-open-file (str file :direction :input)
        (do ((line (read str nil 'eof)
                   (read str nil 'eof)))
            ((eql line 'eof))
          (setf lst (cons line lst))))
      lst)))

(defun distance (as bs sdevs)
  (sqrt (sum (mapcar #'(lambda (a b sdev)
                         (expt (/ (- a b) sdev) 2))
                     as bs sdevs))))

(defun closeness (val entry using sdevs)
  (if (not (null val))
    (let ((sum 0))
      (dolist (element using)
        (if (and (not (= (nth element sdevs) 0)) (numberp (nth element val)) (numberp (nth element entry)))
          (setf sum (+ sum (/ (abs (- (nth element val) (nth element entry))) (nth element sdevs))))))
      sum)))

(defun slow-nearest-neighbor (data entry using k)
  (let ((test (remove entry data)) (nearest nil) (best nil) (sdevs (stddev-list (invert-list data))) (i 0))
    (loop
      (when (= i k)
        (return nearest))
      (dolist (val test)
        (if (null best)
            (progn
              (setf nearest (cons val nearest))
              (setf best (closeness val entry using sdevs)))
            (if (< (closeness val entry using sdevs) best)
                (progn
                  (setf nearest (cons val (cdr nearest)))
                  (setf best (closeness val entry using sdevs))))))
      (setf best nil)
      (setf i (+ 1 i))
      (setf test (remove (car nearest) test)))))

(defun lessp (a b)
  (> (car a) (car b)))
#|
a.amessage(a b c)

A B C

(defmethod (something (another B) (something-else C))
  )

operator <<(ostream&
|#
(defun nearest-neighbor (data entry using k)
  (let ((test (remove entry data)) 
        (nearest (create-heap #'lessp))
        (cur-closeness 0) 
        (sdevs (stddev-list (invert-list data))) 
        (result (list )))
    (progn
      (dolist (cur test)
        (setf cur-closeness (closeness cur entry using sdevs))
        (if (< (heap-count nearest) k) 
            (heap-insert nearest (list cur-closeness cur))
            (if (< cur-closeness (car (heap-peek nearest)))
                (progn
                  (heap-remove nearest)
                  (heap-insert nearest (list cur-closeness cur))))))
      (loop
        (when (= 0 (heap-count nearest))
          (return result))
        (setf result (cons (car (cdr (heap-remove nearest))) result))))))

(defun kernel (val entry using sdevs h)
  (exp (/ (- 0 (expt (closeness val entry using sdevs) 2))
          (expt h 2))))

(defun kernel (base sdevs h)
  #'(lambda (value)
      (exp (/ (- (expt (distance base value sdevs) 2))
              (expt h 2)))))
(defun kernel (base sdevs h)
  #'(lambda (value)
      (exp (/ (- (expt (distance base value sdevs) 2))
              (expt h 2)))))

(defun adder (n)
  #'(lambda (x) (+ x n)))

(defun lwa (data entry using h)
  (let ((test (remove entry data)) (k-sum 0.) (k-val-sum 0.) (sdevs (stddev-list (invert-list data))))
    (progn
      (dolist (cur test)
        (setf k-sum (+ k-sum (kernel cur entry using sdevs h)))
        (setf k-val-sum (+ k-val-sum (* (nth 0 cur) (kernel cur entry using sdevs h)))))
      (if (= 0 k-sum)
           0
           (/ k-val-sum k-sum)))))

;Not done yet
(defun lwa (data entry h)
  (let* ((test (remove entry data))
         (sdevs (mapcar #'stddev (invert-list data)))
         (the-kernel (kernel entry sdevs h)))
    (dolist (cur test)
      (funcall the-kernel cur))))
      
(defun nn-expected (data entry using k)
  (let ((nearest (nearest-neighbor data entry using k)))
    (nth-mean nearest 0)))
    
(defun nn-dif (data entry using k)
  (abs (- (nn-expected data entry using k) (nth 0 entry))))

(defun lwa-dif (data entry using h)
  (abs (- (lwa data entry using h) (nth 0 entry))))

(defun nn-stddev (data test using k)
  (let ((difs (list )))
    (progn
      (dolist (entry test)
        (setf difs (cons (nn-dif data entry using k) difs)))
      (stddev difs))))

(defun nn-variance (data test using k)
  (let ((difs (list )))
    (progn
      (dolist (entry test)
        (setf difs (cons (nn-dif data entry using k) difs)))
      (variance difs))))

(defun lwa-variance (data test using k)
  (let ((difs (list )))
    (progn
      (dolist (entry test)
        (setf difs (cons (lwa-dif data entry using k) difs)))
      (variance difs))))

(defun random-elt (choices)
  (elt choices (random (length choices))))

(defun nfold (lst n)
  (let ((dlst lst) (folds (list )))
    (loop
      (when (= (length dlst) 0)
        (return folds))
      (setf folds (cons (list ) folds))
      (dotimes (i n)
        (when (= (length dlst) 0)
          (return folds))
        (setf (car folds) (cons (random-elt dlst) (car folds)))
        (setf dlst (remove (car (car folds)) dlst))))))

(defun n-pieces (list n)
  (let* ((piece-size (/ (length list) n))
         (indices (mapcar #'round (from-step-to 0 piece-size (length list)))))
    (map2 (lambda (a b) (subseq list a b)) indices)))

(argmax (i set)
        (do stuff)
        (down here))


(0 1 2 3 4 5 6 7 8)
(0 5 9)
 
         
      
(defun nfold-with-set (lst n)
  (let ((folds (nfold lst n)) (dlst nil))
    (progn
      (dotimes (i (length folds))
        (setf dlst lst)
        (dolist (val (nth i folds))
          (setf dlst (remove val dlst)))
        (setf (nth i folds) (cons (nth i folds) dlst)))
      folds)))
          
(defun nfold-stddev (lst n using k)
  (let ((flst (nfold-with-set lst n)) (sdevs (list )))
    (progn
      (dolist (fold flst) 
        (setf sdevs (cons (nn-stddev (cdr fold) (car fold) using k) sdevs)))
      sdevs)))

(defun nfold-variance (lst n using k)
  (let ((flst (nfold-with-set lst n)) (vars (list )))
    (progn
      (dolist (fold flst) 
        (setf vars (cons (nn-variance (cdr fold) (car fold) using k) vars)))
      vars)))

(defun nfold-lwa-variance (lst n using k)
  (let ((flst (nfold-with-set lst n)) (vars (list )))
    (progn
      (dolist (fold flst) 
        (setf vars (cons (lwa-variance (cdr fold) (car fold) using k) vars)))
      vars)))

;(setf data (read-lists "F:/programming/cse517a-hw1/auto-mpg.data"))
;(setf data (read-lists "Desktop/auto-mpg.data"))
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (+ 1 i) (nfold-variance data 20 (list 4) (+ 1 i))))      
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (+ 1 i) (nfold-variance data 20 (list 1 2 3 4 5 6) (+ 1 i))))   
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (+ 1 i) (nfold-lwa-variance data 20 (list 1 2 3 4 5 6) (+ 1 i))))  
;(dotimes (i 4) (format t "~a: ~{~a~^, ~}~%" (/ (+ 4 i) 10) (nfold-lwa-variance data 20 (list 1 2 3 4 5 6) (/ (+ 4 i) 10)))) 
;(nfold-lwa-variance data 20 (list 1 2 3 4 5 6) .4)
    
    